#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2019 crane <crane@crane-pc>
#
# Distributed under terms of the MIT license.

"""
给出宽为1高为Ai的木板n条，排成一排，每次上色只能是连续的横或竖并且宽度为1，问最少刷多少次可以使这些木板都上上色

分析：刷的第一步要么是所有的都竖着涂完，要么是先横着把最矮的涂完，如果是第一种，那么ans等于n，如果是第二种，那么ans=最矮的高度+被刷掉最矮的后，新的几段不连续木板最小上色次数，所以用分治可以解决这个问题
"""

def min_fence(fences_height):
    return min_fence_rec(fences_height, 0, len(fences_height))

def min_fence_rec(fences_height, start, end):
    # [start, end), 开闭区间
    if end - start == 1:
        return 1

    # 1:全部竖着刷的次数
    cnt_vertical = end - start

    # 2:下面是先横着着刷的情况的次数

    # 2-1: 先把最短的刷出去
    min_height = min(fences_height[start:end])
    cnt_horizon = min_height

    # 如果横着刷的次数, 已经超过了木棍条数, 横着刷就没有必要下去了
    if cnt_vertical <= cnt_horizon:
        return cnt_vertical

    for idx in range(start, end):
        fences_height[idx] -= min_height

    # 2-2: 计算最短的分割开来的组(还有剩余长度), 递归计算每个组
    idx = start
    while idx < end:
        while idx < end and fences_height[idx]==0:
            idx += 1

        s = idx
        if s == end:
            break

        while idx < end and fences_height[idx]!=0:
            idx += 1
        e = idx

        # [s, e) 是最短fence分割的一个组(组中每个木条都没有被刷完, 还有剩余长度待刷)
        cnt_horizon += min_fence_rec(fences_height, s, e)
        if cnt_vertical <= cnt_horizon:
            return cnt_vertical

    return min(cnt_vertical, cnt_horizon)

    # 两相比较


def test():
    fences_height = [2, 2, 1, 2, 2]
    v = min_fence(fences_height)
    assert v == 3

    fences_height = [5, 1, 1, 5]
    v = min_fence(fences_height)
    assert v == 3

    fences_height = [5, 2, 2, 5]
    v = min_fence(fences_height)
    assert v == 4

    fences_height = [5, 2, 5, 2, 5]
    v = min_fence(fences_height)
    assert v == 5

    fences_height = [5, 2, 5, 2, 5, 2, 5]
    v = min_fence(fences_height)
    assert v == 6

    fences_height = [5, 2, 2, 2, 5, 2, 5]
    v = min_fence(fences_height)
    assert v == 5

    fences_height = [5, 2, 2, 2, 2, 2, 5]
    v = min_fence(fences_height)
    assert v == 4

    fences_height = [100, 2, 2]
    v = min_fence(fences_height)
    assert v == 3

    fences_height = [3, 1, 1]
    v = min_fence(fences_height)
    assert v == 2

    fences_height = [3, 2, 2]
    v = min_fence(fences_height)
    assert v == 3

def main():
    print("start main")
    test()

if __name__ == "__main__":
    main()
